package com.algorithm.grokking;


import com.google.common.collect.Lists;
import org.apache.commons.collections.CollectionUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

/**
 * 二分查找算法实现(目标数一定在列表中的情况）
 * <p>
 * 思路：通过对比有序列表中间值和目标数，得出下一步应该往有序数组的哪一子列表继续对比直到获得最终结果
 */
public class BinarySearch {

    public static Integer solution(List<Integer> nums, int num) {

        if (CollectionUtils.isEmpty(nums)) {
            return null;
        }

        int high = nums.size() - 1;
        int low = 0;

        int midIndex = 0;
        int guess = 0;

        //循环遍历
        while (high < nums.size() && low > -1) {
            midIndex = (high + low) / 2 ;
            guess = nums.get(midIndex);
            //找到目标数，返回索引
            if (guess == num) {
                return midIndex;
                //目前数小于目标数，索引向右滑动
            } else if (guess < num) {
                low = midIndex + 1;
                //目前数大于目标数，索引向左滑动
            } else{
                high = midIndex - 1;
            }
        }
        return null;
    }


    public static void main(String[] args) {

        List<Integer> list = Lists.newArrayList();
        for(int i=0;i<11;i++){
            list.add(i);
        }

        //9
        System.out.println(solution(list,9));

    }

}
